/*
 * Grasp.cpp
 *
 *  Created on: Jul 23, 2012
 *      Author: hugo
 */

#include "Grasp.h"
#include "algorithm"
#include <sys/resource.h>
#include <math.h>
#include <deque>

bool compare_rcl(build_rcl_elem a,build_rcl_elem b){
	return a.second.second < b.second.second;
}

bool compare_pool(pool_elem a,pool_elem b){
	return a.second < b.second;
}

void Tempo_CPU_Grasp(double *seg_CPU_total, double *seg_sistema_total)
{
  long seg_CPU, seg_sistema, mseg_CPU, mseg_sistema;
  struct rusage ptempo;

  getrusage(0,&ptempo);

  seg_CPU = ptempo.ru_utime.tv_sec;
  mseg_CPU = ptempo.ru_utime.tv_usec;
  seg_sistema = ptempo.ru_stime.tv_sec;
  mseg_sistema = ptempo.ru_stime.tv_usec;

 *seg_CPU_total     = (seg_CPU + 0.000001 * mseg_CPU);
 *seg_sistema_total = (seg_sistema + 0.000001 * mseg_sistema);
}

Grasp::Grasp(Instance* _instance,unsigned int _seed) {
	instance = _instance;
	bestsol=NULL;
	seed=_seed;
	stddev=0;
	time=0;
}

Grasp::~Grasp() {
	// TODO Auto-generated destructor stub
}

double Grasp::get_time(){
	return time;
}

Solution* Grasp::get_solution(){
	return bestsol==NULL?NULL:bestsol->get_solution();
}

vector<Vertex*> Grasp::bfs(LocalSol *sol,int v_id,int depth){
	int* visited = (int*) malloc(sizeof(int)*instance->num_vertex());
	for(int i=0;i<instance->num_vertex();i++){
		if(sol->has_vertex(i))
			visited[i]=1;
		else
			visited[i]=0;
	}
	visited[v_id]=1;
	vector<Vertex*> ans = perform_bfs(visited,v_id,depth);
	ans.push_back(instance->get_vertex(v_id));
	free(visited);
	return ans;
}

vector<Vertex*> Grasp::bfs(LocalSol *sol,Vertex *v,int depth){
	return bfs(sol,v->get_id(),depth);
}

vector<Vertex*> Grasp::perform_bfs(int *visited,int v_id,int depth){
	vector<Vertex*> ans;
	typedef pair<int,int> elem;
	deque<elem> fila;
	elem e = make_pair(v_id,0);
	fila.push_back(e);
	while(!fila.empty()){
		e = fila.front();
		fila.pop_front();
		ans.push_back(instance->get_vertex(e.first));
		if(e.second<depth){
			vector<int> nb = instance->neighborhood(e.first);
			for(unsigned int i=0;i<nb.size();i++){
				int j = nb.at(i);
				if(!visited[j]){
    				elem tmp;
				    if(depth==1 && instance->get_vertex(j)->get_prize()==0){
    				    tmp = make_pair(j,e.second);
				    }else{
					    tmp = make_pair(j,e.second+1);
					}
					fila.push_back(tmp);
					visited[j]=1;
				}
			}
		}
	}
	return ans;
}

vector<Vertex*> Grasp::build_random_pool(unsigned int length){
	cout << "Random pool"<<endl;
	vector<Vertex*> all_vertex;
	for(int i=0;i<instance->num_vertex();i++){
		all_vertex.push_back(instance->get_vertex(i));
	}
	for(unsigned int i=0;i<length;i++){
		int n_rand = rand_r(&seed)%(all_vertex.size()-i);
		Vertex *tmp = all_vertex[n_rand];
		all_vertex[n_rand] = all_vertex[all_vertex.size()-i-1];
		all_vertex[all_vertex.size()-i-1] = tmp;
	}
	vector<Vertex*> pool;
	for(unsigned int i=0;i<length;i++){
		pool.push_back(all_vertex[all_vertex.size()-i-1]);
	}
	return pool;
}

vector<Vertex*> Grasp::build_pool(int size){
	cout << "Heuristic pool"<<endl;
	vector<pool_elem> elements;
	for(long i=0;i< instance->num_vertex();i++){
		if(instance->neighborhood(i).size()==0)continue;
		if(instance->get_vertex(i)->get_prize()==0)continue;
		LocalSol *s = new LocalSol(instance);
		s->add_vertex(i);
		vector<Vertex*> nbs = bfs(s,i,4);
		float sum=0;//instance->get_vertex(i)->get_prize();
		for(unsigned int j=0;j<nbs.size();j++){
			//sum+=nbs[j]->get_prize();
			s->add_vertex(nbs[j]);
		}
		s->kruskal();
		for(unsigned int j=0;j<nbs.size();j++){
		    if(s->has_vertex(nbs[j]))
    			sum+=nbs[j]->get_prize();
		}
		    
//		cout << "("<< i << "," << sum << ") , ";
    	elements.push_back(make_pair(i,sum));
		delete s;
	}
	//cout << endl;

	vector<Vertex*> list;
	vector<Vertex*> draw_list;
	float prev_val = -1;
	int draw_pos = -1;
	make_heap(elements.begin(),elements.end(),compare_pool);
	bool draw = false;
	for(int i=0;(i<size || draw) && elements.size()>0;i++){
		Vertex *v = instance->get_vertex(elements.front().first);
		list.push_back(v);
		//cout << "M " <<elements.front().first<< ": "  << elements.front().second << endl;

		if(prev_val==elements.front().second){
			draw=true;
			if(draw_pos<0)
				draw_pos = i-1;
		}else{
			draw=false;
			if(i<size)
				draw_pos = -1;
			prev_val=elements.front().second;
		}


		pop_heap(elements.begin(),elements.end());
		elements.pop_back();

		make_heap(elements.begin(),elements.end(),compare_pool);
	}

	/*cout<< endl << "DRAW POOL: ";
	for(unsigned int i=0;i<list.size();i++)
		cout << list[i]->get_id() << " ,";
	cout << endl;*/
	if(list.size()<size)
	    size = list.size();
	while(draw_pos>=0 && draw_pos<size){
		int elem = draw_pos+rand_r(&seed)%(list.size()-draw_pos);
		Vertex *v = list[draw_pos];
		list[draw_pos] = list[elem];
		list[elem] = v;
		draw_pos++;
	}
	if(list.size()>size)
		list.erase(list.begin()+size,list.end());

	/*cout<< endl << "POOL: ";
	for(unsigned int i=0;i<list.size();i++)
		cout << list[i]->get_id() << " ,";

	cout << endl;*/
	return list;
}

vector<rcl_elem> Grasp::rcl(LocalSol* sol){
	vector<build_rcl_elem> elements;
	//cout << "LIST: ";
	for(long i=0;i< instance->num_vertex();i++){
		if(!sol->has_vertex(i) && sol->has_connection(i)){
			vector<Vertex*> nbs = bfs(sol,i,1);
			LocalSol *s = new LocalSol(instance);
			float sum=instance->get_vertex(i)->get_prize();
			for(unsigned int j=0;j<nbs.size();j++){
				sum+=nbs[j]->get_prize();
				s->add_vertex(nbs[j]);
			}			

			float gain = sum/s->kruskal();
			if(gain>1){
				//cout <<"(" <<i <<","<<gain<<") ; ";
				elements.push_back(make_pair(i,make_pair(nbs,gain)));
			}
			delete s;
		}
	}
	//cout << endl;
	vector<rcl_elem> list;
	//cout << "RCL: "<<elements.size()<<endl;
	for(int i=0;i<1 && elements.size()>0;i++){
		make_heap(elements.begin(),elements.end(),compare_rcl);
		Vertex *v = instance->get_vertex(elements.front().first);
		list.push_back(make_pair(v->get_id(),elements.front().second.first));

		pop_heap(elements.begin(),elements.end());
		elements.pop_back();

		//cout << v->get_id() << " ,";
	}
	//cout << endl;
	return list;
}

LocalSol* Grasp::construct(vector<Vertex*> pool,int it){
	LocalSol *sol = new LocalSol(instance);
	Vertex *init = pool[it%pool.size()];
	sol->add_vertex(init);
	int v_best;
	do{
		v_best=-1;
		vector<rcl_elem> list = rcl(sol);
		if(list.size()>0){
			int elem = rand_r(&seed)%list.size();
			v_best = list[elem].first;
			vector<Vertex*> nbs = list[elem].second;
			for(unsigned int i=0;i<nbs.size();i++)
				sol->add_vertex(nbs[i]);
		}
	}while(v_best>=0);
	return sol;
}

void Grasp::full_localsearch(LocalSol** sol){
    bool local_imp=true;
    float cost;
	while(local_imp){
		local_imp=false;
        cost = (*sol)->get_cost();
		for(int i=0;i<instance->num_vertex() && !local_imp;i++){
    		LocalSol *tmp = NULL;
		    if((*sol)->has_vertex(i)){
          		tmp = (*sol)->copy_nodes();
		        tmp->remove_vertex(i);
		        if(tmp->get_cost()<cost){
		          cost = tmp->get_cost();
		          *sol = tmp;
		          local_imp=true;
	            }
	        }else if((*sol)->has_connection(i)){
	          tmp = (*sol)->copy_nodes();
		        tmp->add_vertex(i);
		        if(tmp->get_cost()<cost){
		          cost = tmp->get_cost();
		          *sol = tmp;
		          local_imp=true;
	            }
	        }
		}
	}
}

void Grasp::localsearch(LocalSol** sol){
	float cost = (*sol)->get_cost();
	for(int i=0;i<instance->num_vertex();i++){
		LocalSol *tmp = NULL;
		if((*sol)->has_vertex(i)){
      		tmp = (*sol)->copy_nodes();
			tmp->remove_vertex(i);
			if(tmp->get_cost()<cost){
			  cost = tmp->get_cost();
			  *sol = tmp;
		  }
		}else if((*sol)->has_connection(i)){
		  tmp = (*sol)->copy_nodes();
			tmp->add_vertex(i);
			if(tmp->get_cost()<cost){
			  cost = tmp->get_cost();
			  *sol = tmp;
		  }
		}
		/*else if((*sol)->tmp_add_vertex(i)<cost){
      (*sol)->smart_add_vertex(i);
      cost = (*sol)->get_cost();
		}*/
	}
}

void Grasp::start(int type, int pool_size){
  double s_CPU_inicial, s_CPU_final, s_total_inicial, s_total_final;
	Tempo_CPU_Grasp(&s_CPU_inicial, &s_total_inicial);
	instance->pre_test();
	Tempo_CPU_Grasp(&s_CPU_final, &s_total_final);
	time = s_CPU_final - s_CPU_inicial;
	cout << "Pre Time: "<<time <<endl;
	
	/*cout << "MST test:"<<endl;
	LocalSol *s = new LocalSol(instance);
    for(int i=00;i<instance->num_vertex();++i)
        s->add_vertex(i);
	cout << "Prim: "<< s->prim()<<endl;
	cout << "Kruscal: "<< s->kruskal()<<endl;*/
	//instance->calculate_short_path_prize();
	/*LocalSol *sol = new LocalSol(instance);
	sol->add_vertex(0);
	sol->add_vertex(3);
	sol->add_vertex(2);
	sol->add_vertex(5);
	sol->add_vertex(4);
	sol->print();
	sol->remove_vertex(2);
	sol->print();
	cout << sol->has_vertex(5)<<endl;*/
	float avg = 0;
	float qnt = 0;
	vector<float> values;

	LocalSol *sol = new LocalSol(instance);
	bestsol = sol;
	Vertex *v=NULL;
	for(int i=0;i<instance->num_vertex();++i){
		Vertex *vi = instance->get_vertex(i);
		if(v==NULL || vi->get_prize()>v->get_prize())
			v = vi;
	}
	if(v!=NULL){
		//bestsol->add_vertex(v);
		//bestsol->print();
	}
	//getchar();
	vector<Vertex*> pool;

	if(type==0)
		pool = build_pool(pool_size);
	else
		pool = build_random_pool(pool_size);

    /*int golden = instance->get_golden_node();
    if(golden>=0)
        pool.push_back(instance->get_vertex(golden));*/
	for(int it=0;it<pool.size();it++){
		sol = construct(pool,it);
		if(sol->get_cost()<bestsol->get_cost())
			bestsol = sol;
			
		cout << pool[it]->get_id() << ": "<<sol->get_cost() <<endl;
        
		avg += sol->get_cost();
		qnt++;
		values.push_back(sol->get_cost());
	}
	cout << "Pre Solution cost: "<< bestsol->get_cost() << endl;
	localsearch(&bestsol);
	//full_localsearch(&bestsol);
	Tempo_CPU_Grasp(&s_CPU_final, &s_total_final);
	time = s_CPU_final - s_CPU_inicial;
	
	//bestsol->get_solution()->print();

	if(qnt>0){
		avg = avg/qnt;
		float sum=0;
		for(int i=0;i<qnt;i++)
			sum+=(avg-values[i])*(avg-values[i]);
		stddev = sqrt(sum/qnt);
	}
}

double Grasp::get_stddev(){
	return stddev;
}
